{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0I-Es-jovJzm"
   },
   "source": [
    "# 第18章 概率潜在语义分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.概率潜在语义分析是利用概率生成模型对文本集合进行话题分析的方法。概率潜在语义分析受潜在语义分析的启发提出两者可以通过矩阵分解关联起来。\n",
    "\n",
    "给定一个文本集合，通过概率潜在语义分析，可以得到各个文本生成话题的条件概率分布，以及各个话题生成单词的条件概率分布。\n",
    "\n",
    "概率潜在语义分析的模型有生成模型，以及等价的共现模型。其学习策略是观测数据的极大似然估计，其学习算法是EM算法。\n",
    "\n",
    "2.生成模型表示文本生成话题，话题生成单词从而得到单词文本共现数据的过程；假设每个文本由一个话题分布决定，每个话题由一个单词分布决定。单词变量$w$与文本变量$d$是观测变量话题变量$z$是隐变量。生成模型的定义如下：\n",
    "$$P ( T ) = \\prod _ { ( w , d ) } P ( w , d ) ^ { n ( w , d ) }$$\n",
    "\n",
    "$$P ( w , d ) = P ( d ) P ( w | d ) = P ( d ) \\sum _ { \\alpha } P ( z | d ) P ( w | z )$$\n",
    "3.共现模型描述文本单词共现数据拥有的模式。共现模型的定义如下：\n",
    "$$P ( T ) = \\prod _ { ( w , d ) } P ( w , d ) ^ { n ( w , d ) }$$\n",
    "\n",
    "$$P ( w , d ) = \\sum _ { z \\in Z } P ( z ) P ( w | z ) P ( d | z )$$\n",
    "\n",
    "4.概率潜在语义分析的模型的参数个数是$O ( M \\cdot K + N \\cdot K )$。现实中$K \\ll M$，所以概率潜在语义分析通过话题对数据进行了更简洁地表示，实现了数据压缩。\n",
    "\n",
    "5.模型中的概率分布$P ( w | d )$可以由参数空间中的单纯形表示。$M$维参数空间中，单词单纯形表示所有可能的文本的分布，在其中的话题单纯形表示在$K$个话题定义下的所有可能的文本的分布。话题单纯形是单词单纯形的子集，表示潜在语义空间。\n",
    "\n",
    "6.概率潜在语义分析的学习通常采用EM算法通过迭代学习模型的参数，$P ( w | z )$\n",
    "和$P ( z| d )$，而$P（d）$可直接统计得出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "EeHek0KrvNbO"
   },
   "source": [
    "----\n",
    "概率潜在语义分析（probabilistic latent semantic analysis, PLSA）,也称概率潜在语义索引（probabilistic latent semantic indexing, PLSI）,是一种利用概率生成模型对文本集合进行话题分析的无监督学习方法。\n",
    "\n",
    "模型最大特点是用隐变量表示话题，整个模型表示文本生成话题，话题生成单词，从而得到单词-文本共现数据的过程；假设每个文本由一个话题分布决定，每个话题由一个单词分布决定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZpnNY-eRwjq3"
   },
   "source": [
    "### **18.1.2 生成模型**\n",
    "\n",
    "假设有单词集合 $W = $ {$w_{1}, w_{2}, ..., w_{M}$}， 其中M是单词个数；文本（指标）集合$D = $ {$d_{1}, d_{2}, ..., d_{N}$}, 其中N是文本个数；话题集合$Z = $ {$z_{1}, z_{2}, ..., z_{K}$}，其中$K$是预先设定的话题个数。随机变量 $w$ 取值于单词集合；随机变量 $d$ 取值于文本集合，随机变量 $z$ 取值于话题集合。概率分布 $P(d)$、条件概率分布 $P(z|d)$、条件概率分布 $P(w|z)$ 皆属于多项分布，其中 $P(d)$ 表示生成文本 $d$ 的概率，$P(z|d)$ 表示文本 $d$ 生成话题 $z$ 的概率，$P(w|z)$ 表示话题 $z$ 生成单词 $w$ 的概率。\n",
    "\n",
    "   每个文本 $d$ 拥有自己的话题概率分布 $P(z|d)$，每个话题 $z$ 拥有自己的单词概率分布 $P(w|z)$；也就是说**一个文本的内容由其相关话题决定，一个话题的内容由其相关单词决定**。\n",
    "   \n",
    "   生成模型通过以下步骤生成文本·单词共现数据：  \n",
    "   （1）依据概率分布 $P(d)$，从文本（指标）集合中随机选取一个文本 $d$ , 共生成 $N$  个文本；针对每个文本，执行以下操作；  \n",
    "   （2）在文本$d$ 给定条件下，依据条件概率分布 $P(z|d)$, 从话题集合随机选取一个话题 $z$, 共生成 $L$ 个话题，这里 $L$ 是文本长度；  \n",
    "   （3）在话题 $z$ 给定条件下，依据条件概率分布 $P(w|z)$ , 从单词集合中随机选取一个单词 $w$. \n",
    "   \n",
    " 注意这里为叙述方便，假设文本都是等长的，现实中不需要这个假设。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_YwFFCuCgugI"
   },
   "source": [
    "生成模型中， 单词变量 $w$ 与文本变量 $d$ 是观测变量， 话题变量 $z$ 是隐变量， 也就是说模型生成的是单词-话题-文本三元组合 ($w, z ,d$)的集合， 但观测到的单词-文本二元组 （$w, d$）的集合， 观测数据表示为单词-文本矩阵 $T$的形式，矩阵 $T$ 的行表示单词，列表示文本， 元素表示单词-文本对（$w, d$）的出现次数。  \n",
    "\n",
    "从数据的生成过程可以推出，文本-单词共现数据$T$的生成概率为所有单词-文本对($w,d$)的生成概率的乘积：  \n",
    "\n",
    "$P(T) = \\prod_{w,d}P(w,d)^{n(w,d)}$  \n",
    "\n",
    "这里 $n(w,d)$ 表示 ($w,d$)的出现次数，单词-文本对出现的总次数是 $N*L$。 每个单词-文本对（$w,d$）的生成概率由一下公式决定：  \n",
    "\n",
    "$P(w,d) = P(d)P(w|d)$   \n",
    "\n",
    "$= P(d)\\sum_{z}P(w,z|d)$  \n",
    "\n",
    "$=P(d)\\sum_{z}P(z|d)P(w|z)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rIUH6dILnmQs"
   },
   "source": [
    "### **18.1.3 共现模型**\n",
    "\n",
    "$P(w,d) = \\sum_{z\\in Z}P(z)P(w|z)P(d|z)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JSt5kq4LoFJT"
   },
   "source": [
    "虽然生成模型与共现模型在概率公式意义上是等价的，但是拥有不同的性质。生成模型刻画文本-单词共现数据生成的过程，共现模型描述文本-单词共现数据拥有的模式。  \n",
    "\n",
    "如果直接定义单词与文本的共现概率 $P(w,d)$, 模型参数的个数是 $O(M*N)$, 其中 $M$ 是单词数， $N$ 是文本数。 概率潜在语义分析的生成模型和共现模型的参数个数是 $O(M*K + N*K)$, 其中 $K$ 是话题数。 现实中 $K<<M$, 所以**概率潜在语义分析通过话题对数据进行了更简洁的表示，减少了学习过程中过拟合的可能性**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "I_SM4HMBpocd"
   },
   "source": [
    "### 算法 18.1 （概率潜在语义模型参数估计的EM算法）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HVWrjFktp_UF"
   },
   "source": [
    "输入： 设单词集合为 $W = ${$w_{1}, w_{2},..., w_{M}$}, 文本集合为 $D=${$d_{1}, d_{2},..., d_{N}$}, 话题集合为 $Z=${$z_{1}, z_{2},..., z_{K}$}, 共现数据 $\\left \\{ n(w_{i}, d_{j}) \\right \\}, i = 1,2,..., M, j = 1,2,...,N;$  \n",
    "\n",
    "输出： $P(w_{i}|z_{k})$ 和 $P(z_{k}|d_{j})$.\n",
    "\n",
    "1. 设置参数 $P(w_{i}|z_{k})$ 和 $P(z_{k}|d_{j})$ 的初始值。\n",
    "\n",
    "2. 迭代执行以下E步，M步，直到收敛为止。  \n",
    "\n",
    " E步：  \n",
    "    $P(z_{k}|w_{i},d_{j})=\\frac{P(w_{i}|z_{k})P(z_{k}|d_{j})}{\\sum_{k=1}^{K}P(w_{i}|z_{k})P(z_{k}|d_{j})}$  \n",
    "  \n",
    " M步：  \n",
    "    $P(w_{i}|z_{k})=\\frac{\\sum_{j=1}^{N}n(w_{i},d_{j})P(z_{k}|w_{i},d_{j})}{\\sum_{m=1}^{M}\\sum_{j=1}^{N}n(w_{m},d_{j})P(z_{k}|w_{m},d_{j})}$  \n",
    "    \n",
    "    $P(z_{k}|d_{j}) = \\frac{\\sum_{i=1}^{M}n(w_{i},d_{j})P(z_{k}|w_{i},d_{j})}{n(d_{j})}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "M1DKiR8_wJox"
   },
   "source": [
    "#### 习题 18.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "m7xWyhIou6St"
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 215
    },
    "colab_type": "code",
    "id": "D0OLpdWcwOGd",
    "outputId": "021c288f-95c7-4451-ab71-49c568c4598a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 1, 1, 0, 0, 0, 0, 0],\n",
       "       [0, 0, 0, 0, 0, 1, 0, 0, 1],\n",
       "       [0, 1, 0, 0, 0, 0, 0, 1, 0],\n",
       "       [0, 0, 0, 0, 0, 0, 1, 0, 1],\n",
       "       [1, 0, 0, 0, 0, 1, 0, 0, 0],\n",
       "       [1, 1, 1, 1, 1, 1, 1, 1, 1],\n",
       "       [1, 0, 1, 0, 0, 0, 0, 0, 0],\n",
       "       [0, 0, 0, 0, 0, 0, 1, 0, 1],\n",
       "       [0, 0, 0, 0, 0, 2, 0, 0, 1],\n",
       "       [1, 0, 1, 0, 0, 0, 0, 1, 0],\n",
       "       [0, 0, 0, 1, 1, 0, 0, 0, 0]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = [[0,0,1,1,0,0,0,0,0], \n",
    "     [0,0,0,0,0,1,0,0,1], \n",
    "     [0,1,0,0,0,0,0,1,0], \n",
    "     [0,0,0,0,0,0,1,0,1], \n",
    "     [1,0,0,0,0,1,0,0,0], \n",
    "     [1,1,1,1,1,1,1,1,1], \n",
    "     [1,0,1,0,0,0,0,0,0], \n",
    "     [0,0,0,0,0,0,1,0,1], \n",
    "     [0,0,0,0,0,2,0,0,1], \n",
    "     [1,0,1,0,0,0,0,1,0], \n",
    "     [0,0,0,1,1,0,0,0,0]]\n",
    "X = np.asarray(X);X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "rz5CHJLSxWs0",
    "outputId": "e4a614fc-21ca-42af-df12-6f57657b04ab"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11, 9)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 179
    },
    "colab_type": "code",
    "id": "5LwECryz-Gp5",
    "outputId": "918425d3-7323-4a18-86da-9b78b298a1f3"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0],\n",
       "       [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],\n",
       "       [1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0],\n",
       "       [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],\n",
       "       [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],\n",
       "       [0, 1, 0, 0, 1, 1, 0, 0, 2, 0, 0],\n",
       "       [0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0],\n",
       "       [0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0],\n",
       "       [0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = X.T;X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "zoRNiZHYxZ1j"
   },
   "outputs": [],
   "source": [
    "class PLSA:\n",
    "    def __init__(self, K, max_iter):\n",
    "        self.K = K\n",
    "        self.max_iter = max_iter\n",
    "\n",
    "    def fit(self, X):\n",
    "        n_d, n_w = X.shape\n",
    "\n",
    "        # P(z|w,d)\n",
    "        p_z_dw = np.zeros((n_d, n_w, self.K))\n",
    "\n",
    "        # P(z|d)\n",
    "        p_z_d = np.random.rand(n_d, self.K)\n",
    "\n",
    "        # P(w|z)\n",
    "        p_w_z = np.random.rand(self.K, n_w)\n",
    "\n",
    "        for i_iter in range(self.max_iter):\n",
    "            # E step\n",
    "            for di in range(n_d):\n",
    "                for wi in range(n_w):\n",
    "                    sum_zk = np.zeros((self.K))\n",
    "                    for zi in range(self.K):\n",
    "                        sum_zk[zi] = p_z_d[di, zi] * p_w_z[zi, wi]\n",
    "                    sum1 = np.sum(sum_zk)\n",
    "                    if sum1 == 0:\n",
    "                        sum1 = 1\n",
    "                    for zi in range(self.K):\n",
    "                        p_z_dw[di, wi, zi] = sum_zk[zi] / sum1\n",
    "\n",
    "            # M step\n",
    "\n",
    "            # update P(z|d)\n",
    "            for di in range(n_d):\n",
    "                for zi in range(self.K):\n",
    "                    sum1 = 0.\n",
    "                    sum2 = 0.\n",
    "\n",
    "                    for wi in range(n_w):\n",
    "                        sum1 = sum1 + X[di, wi] * p_z_dw[di, wi, zi]\n",
    "                        sum2 = sum2 + X[di, wi]\n",
    "\n",
    "                    if sum2 == 0:\n",
    "                        sum2 = 1\n",
    "                    p_z_d[di, zi] = sum1 / sum2\n",
    "\n",
    "            # update P(w|z)\n",
    "            for zi in range(self.K):\n",
    "                sum2 = np.zeros((n_w))\n",
    "                for wi in range(n_w):\n",
    "                    for di in range(n_d):\n",
    "                        sum2[wi] = sum2[wi] + X[di, wi] * p_z_dw[di, wi, zi]\n",
    "                sum1 = np.sum(sum2)\n",
    "                if sum1 == 0:\n",
    "                    sum1 = 1\n",
    "                    for wi in range(n_w):\n",
    "                        p_w_z[zi, wi] = sum2[wi] / sum1\n",
    "\n",
    "        return p_w_z, p_z_d\n",
    "\n",
    "\n",
    "# https://github.com/lipiji/PG_PLSA/blob/master/plsa.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mujaObW481zI"
   },
   "outputs": [],
   "source": [
    "model = PLSA(2, 100)\n",
    "p_w_z, p_z_d = model.fit(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 89
    },
    "colab_type": "code",
    "id": "EGrRJHeCCEBw",
    "outputId": "6a0fb7f5-04aa-4695-f0fa-2295696f9943"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.64238757, 0.05486094, 0.18905573, 0.24047994, 0.41230822,\n",
       "        0.38136674, 0.81525232, 0.74314243, 0.32465342, 0.19798429,\n",
       "        0.72010476],\n",
       "       [0.6337431 , 0.79442181, 0.96755364, 0.22924392, 0.99367301,\n",
       "        0.20277986, 0.40513752, 0.51164374, 0.73750246, 0.22300907,\n",
       "        0.17339099]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_w_z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 215
    },
    "colab_type": "code",
    "id": "SbdVC9ICCKW4",
    "outputId": "acc5f5c0-52d0-4a63-c321-6d890b4751f9"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[7.14884177e-01, 2.85115823e-01],\n",
       "       [5.38307075e-02, 9.46169293e-01],\n",
       "       [1.00000000e+00, 3.40624611e-11],\n",
       "       [1.00000000e+00, 1.12459358e-24],\n",
       "       [1.00000000e+00, 5.00831891e-42],\n",
       "       [1.66511004e-19, 1.00000000e+00],\n",
       "       [1.00000000e+00, 8.02144289e-15],\n",
       "       [1.04149223e-02, 9.89585078e-01],\n",
       "       [5.96793031e-03, 9.94032070e-01]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_z_d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "本章代码来源：https://github.com/hktxt/Learn-Statistical-Learning-Method\n",
    "\n",
    "本文代码更新地址：https://github.com/fengdu78/lihang-code\n",
    "\n",
    "中文注释制作：机器学习初学者公众号：ID:ai-start-com\n",
    "\n",
    "配置环境：python 3.5+\n",
    "\n",
    "代码全部测试通过。\n",
    "![gongzhong](../gongzhong.jpg)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "PLSA.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
